import java.util.*;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-02-27
 * Time:8:44
 */
public class TestMap {

    /**
     * 复制带随机指针的链表
     * https://leetcode-cn.com/problems/copy-list-with-random-pointer/
     */

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            Node tmp = new Node(cur.val);
            map.put(cur,tmp);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 宝石与石头
     * https://leetcode-cn.com/problems/jewels-and-stones/
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        for(int i = 0;i < jewels.length(); i++){
            set.add(jewels.charAt(i));
        }
        for(int i = 0; i < stones.length(); i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }

    /**
     * 旧键盘 (20)
     * https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
     */
    public class Main{
        public void solution(String exp, String act){
            Set<Character> set = new HashSet<>();
            Set<Character> wrong = new HashSet<>();
            for(Character ch : act.toUpperCase().toCharArray()){
                set.add(ch);
            }
            for(Character ch : exp.toUpperCase().toCharArray()){
                if(!set.contains(ch) && !wrong.contains(ch)){
                    System.out.print(ch);
                    wrong.add(ch);
                }
            }
        }

        public void main(String[] args){
            Scanner s = new Scanner(System.in);
            while(s.hasNextLine()){
                String s1 = s.nextLine();
                String s2 = s.nextLine();
                solution(s1,s2);
            }

        }
    }

    /**
     * 前K个高频单词
     * https://leetcode-cn.com/problems/top-k-frequent-words/
     * @param words
     * @param k
     * @return
     */
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        //1.遍历单词获取频率
        for (String word:words) {
            if (map.get(word) == null){
                map.put(word,1);
            }else {
                map.put(word,map.get(word)+1);
            }
        }
        //2.建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });

        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if (minHeap.size() < k){
                minHeap.offer(entry);
            }else {
            Map.Entry<String,Integer> top = minHeap.peek();
            if (top.getValue().compareTo(entry.getValue())==0){
                if (top.getKey().compareTo(entry.getKey())>0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }else if (top.getValue().compareTo(entry.getValue())<0){
                minHeap.poll();
                minHeap.offer(entry);
            }
            }
        }

        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] s = {"the","day","is","sunny","the","the","the","sunny","is","is"};
        List<String> ret = topKFrequent(s,4);
        System.out.println(ret);
    }
}
